<?php
/**
 * User: LRZ
 * Date: 2020/2/24
 * Time: 12:09
 */

/**
 *  14.最长公共前缀
 *
 *  标签：字符串
 *
 *  编写一个函数来查找字符串数组中的最长公共前缀。
 *  如果不存在公共前缀，返回空字符串 ""。
 *
 *  示例 1:
 *      输入: ["flower","flow","flight"]
 *      输出: "fl"
 *  示例 2:
 *
 *      输入: ["dog","racecar","car"]
 *      输出: ""
 *      解释: 输入不存在公共前缀。
 *
 *  说明: 所有输入只包含小写字母 a-z 。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/longest-common-prefix
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$strs = ['flower', 'flow', 'flight'];
$res  = longestCommonPrefix($strs);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function longestCommonPrefix($strs)
{
    $size = count($strs);
    if ($size === 0) {
        return '';
    }
    $ans = $strs[0];
    for ($i = 1; $i < $size; $i++) {
        for ($j = 0; $j < strlen($ans) && $j < strlen($strs[$i]); $j++) {
            if ($ans[$j] !== $strs[$i][$j]) {
                break;
            }
        }
        $ans = substr($ans, 0, $j);
        if ($ans === '') {
            return '';
        }
    }
    return $ans;
}